﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.ListNode206
{
    // ============================ 力扣 206 反转链表
    //题意：反转一个单链表。
    //示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
    //思路:如果定义一个新的链表来实现元素的反转，是对内存空间的浪费。
    //只需要改变链表的next指针的指向，就可以将链表反转
    

    public class ListNode
    {
        public int val;
        public ListNode next;
        public ListNode(int val = 0, ListNode next = null)
        {
            this.val = val;
            this.next = next;
        }
    }
    public class ReverseListNode206
    {
        //双指针法 
        public ListNode ReverseList(ListNode head)
        {
            ListNode cur = head;
            ListNode pre = null;
            ListNode tmp;
            while(cur != null)
            {
                tmp = cur.next;//保存cur的next节点
                cur.next = pre;//反转操作
                //更新双指针
                pre = cur;
                cur = tmp;
                
            }
            return pre;
        }

        //递归法
        public ListNode ReverseList_2(ListNode head)
        {
            //和双指针法初始化一样的逻辑
            //ListNode cur = head;
            //ListNode pre = null;

            return Reverse(null, head);
        }
        public ListNode Reverse(ListNode pre, ListNode cur)
        {
            if (cur == null)
                return pre;
            ListNode tmp = cur.next;
            cur.next = pre;
            // 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
            // pre = cur;
            // cur = temp;
            return Reverse(cur, tmp);
        }
    }

}
